#include "dbclist.h"
#include "memory.h"

template<class ElemType>
DbcList<ElemType>::DbcList()
{
	Status st;
	st = InitList();
	if(st != 1)
		exit(0);
}

template<class ElemType>
Status DbcList<ElemType>::InitList()
{
	this->head = new LNode<ElemType>;
	this->head->next = this->head->pre = this->head;
	return OK;
}

template<class ElemType>
Status DbcList<ElemType>::DestroyList()
{
	struct LNode<ElemType> *p = this->head->next, *q;
	while(p!=this->head)
	{
		q = p;
		p = p -> next;
		std::cout << "free " << q->data << std::endl;
		delete q;
	}
	this->head->next = this->head->pre = this->head;
	return OK;
}

template<class ElemType>
Status DbcList<ElemType>::ClearList()
{
	return this->DestroyList();
}

template<class ElemType>
Status DbcList<ElemType>::ListEmpty()
{
	return (this->head->next == this->head);
}

template<class ElemType>
int DbcList<ElemType>::ListLength()
{
	struct LNode<ElemType> *p = this->head->next;
	int length = 0;
	while(p != this->head)
	{
		p = p->next;
		length++;
	}
	return length;
}

template<class ElemType>
int DbcList<ElemType>::LocateElem(ElemType e, bool (*func)(ElemType, ElemType))
{
	struct LNode<ElemType> *p = this->head->next;
	int count = 1;
	while(p != this->head)
	{
		if((*func)(p->data, e))
			break;
		p = p->next;
		count++;
	}
	if(p == this->head)
		return 0;
	else
		return count;
}

template<class ElemType>
ElemType DbcList<ElemType>::PriorElem(ElemType cur_e)
{
	struct LNode<ElemType> *p = this->head->next;
	if(p->data == cur_e)
		return p->pre->pre->data;
	while(p != this->head)
	{
		if(p->data == cur_e)
			return p->pre->data;
		p = p->next;
	}
	if(p->next == this->head)
		exit(ERROR);
	return ERROR;
}

template<class ElemType>
ElemType DbcList<ElemType>::NextElem(ElemType cur_e)
{
	struct LNode<ElemType> *p = this->head->next;
	while(p->next != this->head)
	{
		if(p->data == cur_e)
			return p->next->data;
		p = p->next;
	}
	if(p->data == cur_e)
		return p->next->next->data;
	else
		exit(ERROR);
}

template<class ElemType>
ElemType DbcList<ElemType>::GetElem(int i)
{
	struct LNode<ElemType> *p = this->head->next;
	int j;
	for(j = 1; (p != this->head) && j < i; j++)
		p = p->next;
	if((p == this->head) || j>i)
	{
		ElemType error;
		memset(&error, 0, sizeof(error));
		return error;
	}
	return p->data;
}

template<class ElemType>
Status DbcList<ElemType>::ListInsert(ElemType e)
{
	int i;
	if(this->reverse == false)
		for(i = 1; (i<=this->ListLength()) && (this->GetElem(i) < e); i++);
	else
		for(i = 1; (i<=this->ListLength()) && (this->GetElem(i) > e); i++);


	struct LNode<ElemType> *p = this->head, *s;
	int j;
	for(j = 0; (p->next != this->head) && j < i-1; j++)
		p = p->next;
	if(j > i-1)
		return ERROR;
	s = new LNode<ElemType>;
	s->data = e;
	s->next = p->next;
	p->next = s;
	s->pre = p;
	s->next->pre = s;
	return OK;
}

template<class ElemType>
ElemType DbcList<ElemType>::ListDelete(int i)
{
	struct LNode<ElemType> *p = (this->head), *q;
	ElemType t;
	int j;
	for(j = 0; (p->next != this->head) && j < i-1; j++)
		p = p->next;
	if((p->next == this->head) || j > i-1)
		exit(ERROR);
	q = p->next;
	p->next = q->next;
	q->next->pre = p;
	t = q->data;
	delete q;
	return t;
}

template<class ElemType>
Status DbcList<ElemType>::ListTraverse(void (*func)(ElemType))
{
	struct LNode<ElemType> *p = (this->head);
	p = p->next;
	while(p != this->head)
	{
		func(p->data);
		p = p->next;
	}
	return OK;
}

//输出所有元素
template<class ElemType>
void DbcList<ElemType>::Show()
{
	struct LNode<ElemType> *p = (this->head);
	p = p->next;
	while(p != this->head)
	{
		std::cout << (p->data);
		p = p->next;
	}
	return;
}